//请你设计一个用于存储字符串计数的数据结构，并能够返回计数最小和最大的字符串。 
//
// 实现 AllOne 类： 
//
// 
// AllOne() 初始化数据结构的对象。 
// inc(String key) 字符串 key 的计数增加 1 。如果数据结构中尚不存在 key ，那么插入计数为 1 的 key 。 
// dec(String key) 字符串 key 的计数减少 1 。如果 key 的计数在减少后为 0 ，那么需要将这个 key 从数据结构中删除。测试用例
//保证：在减少计数前，key 存在于数据结构中。 
// getMaxKey() 返回任意一个计数最大的字符串。如果没有元素存在，返回一个空字符串 "" 。 
// getMinKey() 返回任意一个计数最小的字符串。如果没有元素存在，返回一个空字符串 "" 。 
// 
//
// 
//
// 示例： 
//
// 
//输入
//["AllOne", "inc", "inc", "getMaxKey", "getMinKey", "inc", "getMaxKey", 
//"getMinKey"]
//[[], ["hello"], ["hello"], [], [], ["leet"], [], []]
//输出
//[null, null, null, "hello", "hello", null, "hello", "leet"]
//
//解释
//AllOne allOne = new AllOne();
//allOne.inc("hello");
//allOne.inc("hello");
//allOne.getMaxKey(); // 返回 "hello"
//allOne.getMinKey(); // 返回 "hello"
//allOne.inc("leet");
//allOne.getMaxKey(); // 返回 "hello"
//allOne.getMinKey(); // 返回 "leet"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= key.length <= 10 
// key 由小写英文字母组成 
// 测试用例保证：在每次调用 dec 时，数据结构中总存在 key 
// 最多调用 inc、dec、getMaxKey 和 getMinKey 方法 5 * 10⁴ 次 
// 
// Related Topics 设计 哈希表 链表 双向链表 👍 147 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class _432_AllOoneDataStructure {
    public static void main(String[] args) {
        AllOne allOne = new _432_AllOoneDataStructure().new AllOne();
//        allOne.inc("hello");
//        allOne.inc("hello");
//        System.out.println(allOne.getMaxKey()); // 返回 "hello"
//        System.out.println(allOne.getMinKey()); // 返回 "hello"
//        allOne.inc("leet");
//        System.out.println(allOne.getMaxKey()); // 返回 "hello"
//        System.out.println(allOne.getMinKey()); // 返回 "leet"

//        allOne.inc("hello");
//        allOne.inc("goodbye");
//        allOne.inc("hello");
//        allOne.inc("hello");
//        System.out.println(allOne.getMaxKey());
//        allOne.inc("leet");
//        allOne.inc("code");
//        allOne.inc("leet");
//
//        allOne.dec("hello");
//
//        allOne.inc("leet");
//        allOne.inc("code");
//        allOne.inc("code");
//
//        System.out.println(allOne.getMaxKey());

        allOne.inc("hello");
        allOne.inc("world");
        allOne.inc("leet");
        allOne.inc("code");
        allOne.inc("ds");
        allOne.inc("leet");
        System.out.println();

    }

    class AllOne {
        private class Node {
            private String key;
            private Node pre;
            private Node next;
            private int count;

            public Node() {
            }

            public Node(String key, int count) {
                this.key = key;
                this.count = count;
            }

            public Node(String key, Node pre, Node next, int count) {
                this.key = key;
                this.pre = pre;
                this.next = next;
                this.count = count;
            }

            private void insert(Node node) {
                Node tmp = this.next;

                tmp.pre = node;
                node.next = tmp;

                this.next = node;
                node.pre = this;


//                node.next = this.next;
//                this.next.pre = node;
//                this.next = node;
//                node.pre = this;
            }

            private void delete() {
                this.pre.next = this.next;
                this.next.pre = this.pre;
            }

            private void exchangeLeft() {
                this.delete();
                this.pre.pre.insert(this);
            }

            private void exchangeRight() {
                this.delete();
                this.next.insert(this);
            }
        }

        private Map<String, Node> map;
        private Node root;
        private Node tail;


        public AllOne() {
            map = new HashMap<>();
            root = new Node("", -1);
            tail = new Node("", -1);
            root.next = tail;
            tail.pre = root;
        }

        public void inc(String key) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.count++;
                if (node.next != tail && node.count > node.next.count) {
                    node.exchangeRight();
                }
            } else {
                Node node = new Node(key, 1);
                root.insert(node);
                map.put(key, node);
            }
        }

        public void dec(String key) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                if (node.count  == 1) {
                    node.delete();
                } else {
                    node.count--;
                    if (node.pre != root && node.count < node.pre.count) node.exchangeLeft();
                }
            } else {
                System.out.println("不可能不包含，所以这句话不执行");
            }
        }

        public String getMaxKey() {
            return tail.pre.key;
        }

        public String getMinKey() {
            return root.next.key;
        }
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    // 这里是错的，要用链表
    class AllOne1 {
        private Map<String, Integer> map;
        private Deque<String> stMax;
        private Deque<String> stMin;

        public AllOne1() {
            map = new HashMap<>();
            stMax = new ArrayDeque<>();
            stMin = new ArrayDeque<>();
        }

        public void inc(String key) {
            if (!map.containsKey(key)) {
                map.put(key, 1);
            } else {
                map.put(key, map.get(key) + 1);
            }
        }

        public void dec(String key) {
            if (map.get(key) == 1) {
                map.remove(key);
            } else {
                map.put(key, map.get(key) - 1);
            }
        }

        public String getMaxKey() {
            return null;
        }

        public String getMinKey() {
            return null;
        }
    }

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */
//leetcode submit region end(Prohibit modification and deletion)

}